We consider the following single-machine scheduling problem, which is oftendenoted $1||\sum f_{j}$: we are given $n$ jobs to be scheduled on a singlemachine, where each job $j$ has an integral processing time $p_j$, and there isa nondecreasing, nonnegative cost function $f_j(C_{j})$ that specifies the costof finishing $j$ at time $C_{j}$; the objective is to minimize $\sum_{j=1}^nf_j(C_j)$. Bansal \& Pruhs recently gave the first constant approximationalgorithm with a performance guarantee of 16. We improve on this result bygiving a primal-dual pseudo-polynomial-time algorithm based on the recentlyintroduced knapsack-cover inequalities. The algorithm finds a schedule of costat most four times the constructed dual solution. Although we show that thisbound is tight for our algorithm, we leave open the question of whether theintegrality gap of the LP is less than 4. Finally, we show how the techniquecan be adapted to yield, for any $\epsilon >0$, a $(4+\epsilon )$-approximationalgorithm for this problem.
展开▼
